/**冒泡排序
 * 比较所有相邻的元素，如意第一个比第二个大，则交换它们
 * 一轮下来，可以保证最后一个数是最大的
 * 执行 n-1 轮，就可以完成排序
*/
Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        [this[j], this[j + 1]] = [this[j + 1], this[j]]
      }
    }
  }
}

const arr = [5, 4, 3, 3, 32, 1]
arr.bubbleSort()
console.log(arr, '----冒泡')

// 时间复杂度：O(n^2)
// 但是冒泡排序性能很差，基本上在工作中很少用到，大多还是在面试中出现

/** 选择排序
 * 找到数组中的最小值，选中它并将其将其放置在第一位
 * 接着找到第二小的值，选中它并将其放置在第二位
 * 以此类推，执行 n-1 轮
 */
Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let indexMin = i
    for (let j = i; j < this.length; j++) {
      if (this[j] < this[indexMin]) {
        indexMin = j
      }
    }
    if (indexMin !== i) {
      [this[i], this[indexMin]] = [this[indexMin], this[i]]
    }
  }
}
const arr1 = [5, 4, 3, 3, 32, 1]
arr1.selectionSort()

console.log(arr1, '----选择')

// 两个嵌套循环，时间复杂度：O(n^2)
// 选择排序同冒泡排序一样性能很差，基本上在工作中很少用到，大多还是在面试中出现


/** 插入排序
 * 从第二个数开始往前比
 * 比它大的就往后排
 * 以此类推进行到最后一个数
 */

Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i++) {
    const temp = this[i]
    let j = i
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1]
      } else {
        break
      }
      j--
    }
    this[j] = temp
  }
}

const arr2 = [5, 4, 3, 3, 32, 1]
arr2.insertionSort()

console.log(arr2, '----插入')
// 两个嵌套循环，时间复杂度：O(n^2)
// 插入排序性能比冒泡和选择性能好点

// 归并排序
/**
 * 分： 把数组劈成两半，再递归地对子数组进行‘分’操作，直到分成一个个单独的数dierbu
 * 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组
 * 那么如何合并两个有序数组：
 * 1，新建一个空数组res,用于存放最终排序后的数组
 * 2，比较两个有序数组的头部，较小者出队并推入res中
 * 3，如果两个数组还有值，就重复第二步
 */

Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, arr.length)
    const orderLeft = rec(left)
    const orderRight = rec(right)
    const res = []
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res = rec(this)
  res.forEach((n, i) => { this[i] = n })
}

const arr3 = [5, 4, 3, 3, 32, 1]
arr3.mergeSort()
console.log(arr3, '----合并')